package sort

/*
	k 桶的个数
	平均时间复杂度：O(n+k)
	最好情况：O(n+k)
	最坏情况：O(n+k)
	空间复杂度：O(k) 需要一个栈的空间来递归
	排序方式：Outplace
	稳定性：稳定
*/
func CountSort(nums []int) []int {
	max := nums[0]
	for _, v := range nums {
		if v > max {
			max = v
		}
	}

	count := make([]int, max+1)

	// 记录各元素对应的个数
	for _, v := range nums {
		count[v]++
	}

	// 变形：等于前面的个数之和
	for i := 1; i < len(count); i++ {
		count[i] += count[i-1]
	}

	res := make([]int, len(nums))

	for i := len(nums) - 1; i >= 0; i-- {
		index := count[nums[i]] - 1 // 索引为count-1
		res[index] = nums[i]
		count[nums[i]]--
	}

	return res
}
